#include <stdio.h>
#include <stdlib.h>

/*
队列 的链式实现
*/

// 带头结点  front指向队头头节点 rear指向队尾元素

typedef struct LNode
{
    int data;
    struct LNode *next;
};

typedef struct // 链式队列
{
    LNode *front, *rear;  // 队尾队头指针

}LinkQueue;

void InitQueue(LinkQueue &LQ)
{
    LNode *n = (LNode *)malloc(sizeof(LNode));  // 头结点

    LQ.front = LQ.rear = n;  // 队列头尾初始指向头结点
    LQ.front->next = NULL;

}

bool isEmpty(LinkQueue LQ)
{
    return LQ.front->next == NULL;
}

// bool isFull(LinkQueue LQ)  搞笑
// {
//     return LQ.rear->next == LQ.front;
// }

bool EnQueue(LinkQueue &LQ, int x)
{
    LNode *n = (LNode *)malloc(sizeof(LNode));
    n->next = NULL;
    n->data = x;
    // if(LQ.front == NULL)  // 第一个入队元素 Q.front 一直指向头结点不变
    // {
    //     LQ.rear->next = n;  // 队尾入队
    //     return true;
    // }
    LQ.rear->next = n;
    LQ.rear = n;  // 指向当前队尾节点
    return true;


}

bool DeQueue(LinkQueue &LQ, int &x)
{
    if(isEmpty(LQ))
    {
        return false;
    }

    LNode *p;
    p = LQ.front->next;
    x = p->data;

    LQ.front->next = p->next;  // 头指针指向下一个元素

    if(LQ.rear == p)  // 出队元素为最后一个元素
    {
        LQ.rear == LQ.front;  
    }
    free(p);  // 释放空间
    return true;
}

bool GetHead(LinkQueue LQ, int &x)
{
    if(isEmpty(LQ))
    {
        return false;
    }
    LNode *p;
    p = LQ.front->next;
    x = p->data;
    return true;
}

void show(LinkQueue LQ)
{
    puts("show...");
    LNode *p;
    p = LQ.front->next;
    while(p)
    {
        printf("%i -> ", p->data);
        p = p->next;
    }
    
}

void testLiQueue()
{
    LinkQueue LQ;
    puts("init...");
    InitQueue(LQ);
    show(LQ);

    puts("enter...");
    EnQueue(LQ, 1);
    EnQueue(LQ, 2);
    EnQueue(LQ, 3);
    show(LQ);

    puts("de queue...");
    int x;
    DeQueue(LQ, x);
    printf("%i", x);
    show(LQ);
    puts("");

}

int main()
{
    testLiQueue();
    return 0;
}






